/**
 * 项目名称: Topic_450.cpp
 * 项目路径: study/DataStructure/LeetCode/树/中等
 * 编辑时间: 2024年08月29日07时42分12秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        del(root,key);
        return root;
    }
    void del(TreeNode *& root,int key){
        if(!root)return;
        if(key == root->val){
            if(!root->left && !root->right)root = nullptr;//让子节点等空,表示删除节点
            else if(!root->left) root = root->right;//只有右儿子
            else if(!root->right)root = root->left;//只有左儿子
            else{//左右儿子都有
                auto p = root->right;
                while (p->left)p=p->left;
                root->val = p->val;
                del(root->right,p->val);
            }
        }
        else if(key < root->val)del(root->left,key);
        else del(root->right,key);
    }
};
